백준 9935 문자열 폭발

백준 문자열 폭발은 문자열과 폭발 문자열이 주어지고 폭발 문자열을 입력받아 이 폭발문자열을 터뜨려 나온 최종 문자열을 구하는 문제이다. 폭발 문자열이 터져서 또한번 폭발문자열을 이룰 수 있으니 이점에 주의하여 풀어야 한다.

처음에는 단순히 str.find(“폭발문자열”)을 찾아 서브 스트링으로 조합한뒤 찾을 문자열이 없을때 까지 진행했는데 이 방법은 시간초과가 발생하였다. find 함수는 O(mn)의 시간복잡도를 가지고 있는데 만약 폭발 문자열의 길이가 2이고 m의 길이의 문자열이 모두 폭발문자열이 될 수 있는 문자열로 이루어져 있다면 O(mn * m/2 )이므로 시간초과에 걸린다.

이 방법은 stack의 동작구조를 이용했는데 맨 마지막에는 순서대로 빼주기 위해서 dequeue를 사용했다. for 문으로 m길이의 문자를 탐색하다가 폭발문자열의 끝자리와 같은 부분을 만나게 되면 일련의 과정을 수행한다.

temp stack을 만들고 폭발문자열의 길이만큼 검사하면서 폭발문자열인지 확인하며 temp stack에 문자열들을 쌓는다. 아니면 temp stack에 있던 원소를 다시 원래대로 돌려놓고 맞다면 아무일도 하지 않고 진행한다.

결과적으로 stack에는 폭발문자열들이 제거된 결과가 생기게 되고 최대 길이 m에 대하여 폭발문자열 n만큼 수행하므로 시간 복잡도는 O(mn)이 된다.

#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<algorithm>
#include<set>
#define INF 987654321
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.txt", "r", stdin);

	deque<char> char_stack;
	
	string str;
	string target;
	cin >> str >> target;

	int str_len = str.length();
	int target_len = target.length();

	int index = 0;

	for (int i = 0; i < str_len; i++)
	{
		if(str[i] != target[target_len-1])
			char_stack.push_back(str[i]);
		else
		{
			char_stack.push_back(str[i]);
			deque<char> temp;

			bool ok = true;
			for (int j = target_len - 1; j >= 0; j--)
			{
				if (target[j] != char_stack.back())
				{
					ok = false;
					break;
				}
				temp.push_back(char_stack.back());
				char_stack.pop_back();
			}

			if (!ok)
			{
				while (!temp.empty())
				{
					char_stack.push_back(temp.back());
					temp.pop_back();
				}
			}
		}
	}

	if(char_stack.empty())
		cout<<"FRULA";
	else
	{

		while (!char_stack.empty())
		{
			cout << char_stack.front();
			char_stack.pop_front();
		}
	}

}